//
// Description: 1583. 统计不开心的朋友
// Created by Loading on 2021/8/14.
//

#include <bits/stdc++.h>

using namespace std;

int unhappyFriends(int n, vector<vector<int>> &preferences, vector<vector<int>> &pairs) {
    // rank[i][j] 表示在 i 中，j 的亲密度排名
    vector<vector<int>> rank(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n - 1; ++j) {
            rank[i][preferences[i][j]] = j;
        }
    }
    // 分组情况
    vector<int> group(n);
    for (auto &pair : pairs) {
        group[pair[0]] = pair[1];
        group[pair[1]] = pair[0];
    }

    int unhappy = 0;
    // 根据排名遍历每组搭档，进行模拟，O(n2)
    for (int i = 0; i < n; ++i) {
        int j = group[i];
        // j 在 i 中的排名
        int rank_ij = rank[i][j];
        // 在排名比 j 靠前的人里寻找
        for (int k = 0; k < rank_ij; ++k) {
            // 寻找排名靠前人的搭档
            int pre = preferences[i][k];
            int match_pre = group[pre];
            // 如果它与 i 的亲密度排名小于它与当前搭档的亲密度排名，i 即为不快乐
            if (rank[pre][i] < rank[pre][match_pre]) {
                unhappy++;
                // 确定不快乐，即可跳出循环，否则可能会出现重复累加
                break;
            }
        }
    }

    return unhappy;
}

int main() {
    int n = 4;
    vector<vector<int>> preferences = {{1, 2, 3},
                                       {3, 2, 0},
                                       {3, 1, 0},
                                       {1, 2, 0}};
    vector<vector<int>> pairs = {{0, 1},
                                 {2, 3}};

    int unhappy = unhappyFriends(n, preferences, pairs);
    cout << unhappy << endl;
}